package backtracking;

import java.util.Scanner;

/**
 * 
 * @author victor
 * 
 */
public class NReinas_Backtracking {

	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		try {
			int numero = Integer.parseInt( sc.nextLine() );
			
			n_reinas( numero );
			
		} catch(Exception e){
			;
		}
	}
	
	/**
	 * 
	 * @param n
	 */
	private static void n_reinas(int n) {
		int[] c = new int[n];

		boolean[] f = new boolean[n];
		for (int i = 0; i < n; i++)
			f[i] = true;

		boolean[] dp = new boolean[2 * n - 1];
		for (int i = 0; i < 2 * n - 1; i++)
			dp[i] = true;

		boolean[] ds = new boolean[2 * n - 1];
		for (int i = 0; i < 2 * n - 1; i++)
			ds[i] = true;

		buscarReinas(n, 0, c, f, dp, ds);
	}

	/**
	 * 
	 * @param n
	 * @param i
	 * @param solucion
	 * @param f
	 * @param dp
	 * @param ds
	 */
	private static void buscarReinas(int n, int i, int[] solucion, boolean[] f, boolean[] dp, boolean[] ds) {
		for (int j = 0; j < n; j++)
			if (f[j] && dp[i - j + n - 1] && ds[i + j]) {
				solucion[i] = j;

				f[j] = false;
				dp[i - j + n - 1] = false;
				ds[i + j] = false;

				if (i == n - 1)
					imprimir(solucion);
				else
					buscarReinas(n, i + 1, solucion, f, dp, ds);

				f[j] = true;
				dp[i - j + n - 1] = true;
				ds[i + j] = true;
			}
	}

	/**
	 * 
	 * @param solucion
	 */
	private static void imprimir(int[] solucion) {
		for (int i = 0; i <= solucion.length; i++)
			System.out.print(solucion[i] + " ");
		System.out.println();
	}
	
}
